package com.kenliang.algorithm.sort;

/**
 * @author KenLiang
 * @description:插入排序 时间复杂度O(N**2),空间复杂度O(1), 相等不交换有稳定性
 * @date Created in 14:54 2021/1/2.
 */
public class InsertSort implements ISort{
    @Override
    public int[] sort(int[] in) {
        //每次循环保证0～i上有序
        for(int i=0;i<in.length;i++){
            //每次循环比较当前值与前一个值比较，小的放前面，直到大于等于前一个数字
            for(int j=i;j>0;j--){
                if(in[j]<in[j-1]){
                    this.swap(in,j,j-1);
                }else{
                    break;
                }
            }
        }
        return in;
    }
}
